AB Substrings
難しそうt6o_o6t.icon
と思ってサンプルケースを見たら、min(Aで終わる文字列,Bで文字列)を取ったら、新たに生まれるABの数はわかりそう。
なにか問題がある
code:bad.cpp
using namespace std;
int main(void)
{
int n = 0, a_end = 0, b_start = 0, ans = 0;
string s;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
{
b_start++;
}
{
a_end++;
}
for (int j = 0; j + 1 < n; j++)
{
if (sj = 'A' && sj + 1 == 'B') {
ans++;
j++;
}
}
}
cout << ans + min(b_start, a_end) << endl;
return 0;
}
..............
なぜ、神は=と==を分けたのでしょうか
ランダムテストを書いたt6o_o6t.icon
サンプルケース3つは普通に通った
問題のあるケースを見つけたt6o_o6t.icon
自分のなかでも、疑問があった部分だ
言語化を避けてはならないのだと思う
Bから始まりAで終わるケースが問題
Aを先に見つけても、Bを先に見つけても、答えは一緒
Bの判定時には、先に見つかったAが存在するか、Aの判定時には、先に見つかったBが存在するかを確認すれば良いと思う
文字列の長さは N ではないt6o_o6t.icon
しばらく気づかなかったt6o_o6t.icon
Runtime Errorは解消できたt6o_o6t.icon
code:bad.cpp
using namespace std;
int main(void)
{
int n = 0, ans = 0;
int a_cnt = 0, b_cnt = 0;
string s;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
int new_a = a_cnt, new_b = b_cnt;
if (start == 'B')
{
if (a_cnt > 0)
{
ans++;
new_a--;
}
else
{
new_b++;
}
}
if (end == 'A')
{
if (b_cnt > 0)
{
ans++;
new_b--;
}
else
{
new_a++;
}
}
a_cnt = new_a, b_cnt = new_b;
for (int j = 0; j + 1 < s.length(); j++)
{
if (sj == 'A' && sj + 1 == 'B') {
ans++;
j++;
}
}
}
cout << ans << endl;
return 0;
}
WA.iconがrand_24とrand_37に残っているt6o_o6t.icon
ランダムテスト1000回回したが見つからなかった
特殊なケースだと思う
特定のパターンを正しく処理できない、とかではなく
入力が$ 10^4個あるパターンは試していない
1000回回して見つかった！
BA
BA
というパターン
AとBを同じ文字列に対して紐づけてはならないのに、2つ分カウントしてしまっている
最後にAとBが見つかった場所を保持して、
最後にAとBが見つかった場所に紐付けるルール
もし、Aの値が
この場合は？
XXA
BA
BA
Queueが良いと思う
カウントだけで良いと思っていたけど、それがいつ増えたのかを確認できたらシンプルに書ける
変なバグを追加してしまった
if文の中だけどfor文のトップレベルな場所で早期continueしてしまった
関数か、他のfor文の中にいるつもりになっていた
良い書き方が分からない
A -> Bで紐づいた場合、
思いついた
$ O(N^2)
文字列を考える
まずBで終わるものを見つけて、追加する
このとき、flagをfalseにする
次にAで始まるものを見つけて..
思いついた
Bで終わるものと、Aで始まるもの、Bで終わりAで始まるもの
それぞれのカウントを保持する
$ x, y, zとする
どうするのが良いか？
Bで終わるもの → Aで始まるもの
zの特徴は、zどうしを繋げていれば良いということ
xとyは、同じ分だけ消費することしかできない
zをxやyに含めることも考えたが、1つの単語で消費してしまう実装をしかねないのでやめた
min(x,y) + zが最適か？
x
B以外の文字で始まり、Aで終わる
y
Bで始まり、A以外の文字で終わる
z
Bで始まりAで終わる
$ x> yの場合
このとき、たとえば CA, BC, CA, BC, BC, BC, BC, BA（2個）
zが存在するなら、それを使い切るのが最適
もし、zが存在したとしても、例えば以下のようにyを後ろに持って行っても変わらない
CA, BC, BC, BC, BC, BC
なぜなら、xとyの組み合わせを1つ消して、zとyの組み合わせを1つ生むのと変わらないから
そういうことではないかもしれない
$ x = yの場合
このとき、
$ x < yの場合
$ x = 0の場合
$ y = 0の場合
xに対してはyが必要だt6o_o6t.icon
zは、yが後ろに来ても良いし、zが前に来ても良い
x
CA
y
BC
z
BA
x, y, zの順だと、 CA BC BAとなって1個
x, z, yの順だと、CA BA BCとなって2個
z, x, yの順だと BA CA BCとなって1個
つまり、AとBを連続させるのが最適
Aが終わりに来るように選ぶのが良い
BがAの次に来るように選ぶのが良い
zがない場合は？
min(x, y)個のABが得られる
xを1個取り出し、次にzを可能な限り並べ、yで終端
xとyが両方1個以上ある場合は？
z + 1個のABが得られる
このとき、xとyをそれぞれ1引き去る
xがありyがない場合は？
z個のABが得られる
xのみ1引き去る
xがなくyがある場合は？
z個のABが得られる
yのみ1引き去る
xとyの両方がない場合は？
例：BA BA
max(z - 1, 0)個のABが得られる
次に、残ったxとyでCA, BC, CA, BCという、非AB文字を挟んだ繰り返しを構成する
max(min(x, y), 0)個のABが得られる
0以下にはならないのでこのように書いた